1.1. Field of the Invention
This invention relates to cryptographic communication in general, and more specifically, to methods and apparatus for securely proving knowledge of a shared small secret password between two parties using messages exchanged across an open is communication channel.
1.2. Description of the Related Art
Passwords are an essential component of secure systems. Although they play a crucial role in authenticating the identity of people to systems, traditional password-based network authentication systems have weaknesses due to improper use of passwords. Such systems often use the password as if it were a cryptographic key, and require the password to be chosen as carefully as one would choose a cryptographic key. One requirement is that the choice be from an effectively large “password-space”. The size of this space is sometimes expressed in terms of a number of bits of “entropy”. For simplicity, we often refer to any low-entropy secret from a space that is vulnerable to dictionary attacks as a “small password”. In practice, due to human limitations, many passwords are small. This is a problem for many systems which can be attacked using a repeated computation using all possible (or likely) guesses for the password. This is known as a brute-force, or dictionary attack.
Dictionary attacks can occur on-line, in an interaction between an attacker and a legitimate user or system. They can also occur off-line, using information gathered by monitoring messages sent between two legitimate parties during an authentication protocol exchange. On-line attacks can often be easily detected and thwarted, by counting bad attempts and denying access. Banking ATM machines thwart attack by retaining the user's card after three bad access attempts. But remote authentication opens the possibility of an off-line attack on the messages transmitted across a network.
As widely available computing power increases, successful off-line dictionary attacks on a small password become easier. Today, ever-increasing computer power has clearly outpaced the (unchanging) ability of people to remember longer passwords. Today, 56-bit symmetric key seem to offer only marginal security. U.S. export regulations have allowed export of 40-bit key systems, presumably because they are breakable. Thus, in many systems, a “safely large password” requires more than 40 bits of entropy, and the number is steadily growing. On the other hand, it seems that many people cannot easily remember and use a password from a space of 32 bits. This is equivalent to a random 10 digit number, about 6 random letters and digits, or a pair of words from an average English dictionary. Several studies over many years have found that a significant percentage of user-chosen passwords can be found with a modest computational effort, having an effective size of less than 30 bits (roughly a billion choices). At one extreme, bank-card PIN numbers have less than 14 bits. Forcing everyone to double or triple the size of their passwords, and expecting them to not write them down, or expecting most people to be comfortable using “pass-phrases”, is denying the inevitable truth. People can't or won't properly handle anything larger than a small password, so systems must protect them from attack. In light of this, most traditional network authentication systems that use passwords are obsolete. Better systems must be designed and deployed that are resistant to off-line dictionary attack, to safely tolerate the use of potentially small passwords.
1.3. Detailed Objective
Our goal is to authenticate one party to the other with a series of messages exchanged across an open network, where interception or modification of the messages by an untrusted third party may be possible. Furthermore, we do not require that either party have access to any additional long-lived keys for either a symmetric or a public-key encryption system—we seek a method based solely on the password. In light of the crucial role of the password, we must protect it as much as possible.
These methods can be used for direct person-to-person authentication, where an appropriate computer or device performs the required protocol computation on behalf of the person. More typically, one of the parties is a host computer. We will refer to the user's computer as “Alice” and the host computer as “Bob”.
We assume that Alice and Bob use a small password as the basis for establishing a secure communication channel between the them, and we assume that an attacker has the computational power to enumerate all possible password values to attempt a dictionary attack. We first desire a method where Alice and Bob prove to each other that they know the same secret. We also desire an extended method where Bob, who only has knowledge of a “hidden-password”, verifies that Alice knows the password. The hidden-password in our extended method will be a specially constructed one-way transformation of the password.
Historically, much attention has focused on the problem of getting Alice to use a large “well-chosen” password. Newer research, such as ours, focuses attention on how to legitimately use a small password for remote authentication across an open insecure network. This must be done without making the password vulnerable to off-line dictionary attack.
1.4. Traditional Methods
Most older methods of remote authentication based on a shared secret do not survive dictionary attacks when the secret is small. In a common example, Alice sends a random number R to Bob, Bob computes a one-way collision-free hash function h of both R and the password S, and sends the result h(R,S) to Alice. Alice also computes h(R,S) and compares it to Bob's result. If they are equal, Bob has proven knowledge of the password to Alice, and because of the hash, the secret password is not directly revealed to a third party who monitors the exchange. The randomness of R prevents replay attacks. However, when the password is small, Eve, an eavesdropper who obtains R and h(R,S), can repeatedly hash each possible password S′ in the dictionary with R, and compare each result h(R,S′) to Bob's response. (The dictionary entries may be either pre-built, or computed as needed.) When a match is found, the attacker knows that S′ is the password.
When tolerance for small passwords is added to all the classic requirements for a secure exchange, most traditional password authentication methods are shown to be obsolete.
Some methods can confirm knowledge of a small shared secret based on the parties' access to other long-lived data. This data may be a large shared secret, or a large public key. There are many general methods for public-key-based authentication. Such schemes pose additional problems such as certifying public-keys, requiring a secure key distribution system, or requiring secure storage for large secret keys. Here we seek methods that are based solely on an easily-memorized secret.
1.5. Minimal Disclosure Methods
A few methods exist that address our goal of preventing off-line dictionary attacks, without requiring access to additional long-lived keys. Examples are the various Encrypted Key Exchange (EKE) methods described by Bellovin & Merritt [BM92] and the “secret public-key” methods described by Gong and others in [GLSN93, Gon95]. An example of an enhancement where Bob stores a one-way function of the password, and verifies that Alice knows the original password, are the A-EKE methods described in [BM94]. These documents are herein incorporated by reference. These methods represent the best of the prior art, and reveal little or no information for an attacker to mount a dictionary attack. We will call these “minimal disclosure” methods, since they minimize disclosure of information about the password to potential attackers.
Another method that is somewhat resistant to passive dictionary attack is called Fortified Key Negotiation (FKN), and is described in [AL94]. We refer to this as a “reduced disclosure” method, since it may leak a considerable amount of information.
These minimal disclosure methods are relatively new, and have not yet been widely deployed in applications.
1.6. Diffie-Hellman Exponential Key Exchange
A common function used in modern cryptographic methods is the Diffie-Hellman exponential key exchange (“DH”) described in [DH79]. This is an example of a public-key distribution system, the purpose of which is to distribute keys to one or more parties using some kind of public-key technique. This is different than a public-key cryptosystem the purpose of which is to typically perform signing and/or sealing operations.
The major limitation of original DH is that it is an unauthenticated public-key exchange—It doesn't prove the identity of either party to the other. It is thus vulnerable to a “man-in-the-middle” attack where a third party, Mallory, performs two distinct DH exchanges with Alice and Bob to create separate encrypted channels. By decrypting and re-encrypting all messages passed between Alice and Bob, Mallory can act as an undetected eavesdropper. Despite this limitation, DH has important uses and the basic computation in DH forms a basis for many well-known security schemes, such as the ElGamal and related public-key crypto-systems, the DSS digital signature standard [NIST94]. Two methods that have incorporated DH to provide an authenticated key exchange are the station-to-station protocol and DH-EKE, one of the Encrypted Key Exchange methods. Our methods will also utilize a DH exchange.
The general construction of DH uses exponentiation within a mathematical group. Although a variety of groups can be used in DH, a common example uses arithmetic in Zp*, the multiplicative group of the Galois field of integers modulo p, where p is a large prime. Zp* is also sometimes written as GF(p)*. The elements (members) of this group are the integers from 1 to p−1, and the group operator (represented by *) is multiplication modulo p. We review the classic DH operation here:                g and p are well-known numbers, where g is a primitive root of p.        Bob chooses a random RB, computes QB=gRB mod p, and sends QB to Alice.        Alice chooses a random RA, computes QA=gRA mod p, and send QA to Bob.        Bob computes K=QARB mod p.        Alice computes K=QBRA mod p.        
The result of the exchange is that both Alice and Bob alone share knowledge of a large key K. They both compute the same value of K because (gRA)RB mod p=(gRB)RA mod p.
DH can also use other groups, including large prime-order subgroups of Zp*, and groups of points on elliptic curves over finite fields. The principal advantage of alternate groups such as elliptic curves lies in their increased resistance to a discrete-log computation for a given computational cost, assuming the current knowledge of discrete log techniques. With elliptic curve groups, the size of the field can be much smaller than the size required with Zp*, and thus fewer bits are needed to represent the group elements.
We will use the term “exponentiation” to broadly refer to repeated applications of the group operator on an element with itself. In some cases, the group operator does not use exponential arithmetic in the integers. For example, the literature on elliptic curve groups traditionally describes the group operator for two points as “addition” of points, and group exponentiation to an integer power is described as “multiplication of a point by an integer”. Further description of elliptic curve groups can be found in [P1363].
Though our discussion will focus on Zp* and it's subgroups, the techniques we will discuss apply to use of DH in any other suitable group with comparable structure. We now briefly review some algebraic results that are relevant to use of the DH in both our method as well as in DH-EKE.
1.7. Selection of DH Parameters g and p, and the Structure of Zp*
The first DH computation (using Zp*) is gR mod p, where g and p are specially chosen, and R is a large random number. Proper selection of g and p is crucial to the DH exponential key exchange, in general, and even more so in password-authenticated DH methods. We will generally limit our discussion to groups where the factorization of p−1 is known, and where p−1 has a large prime factor q. A large prime factor prevents easy solutions to the discrete logarithm problem, and methods to generate such values of p with several hundreds and even thousands of bits are well known to those skilled in the art. It has been recommended that the sizes of R and q be at least twice the number of bits needed in the resulting key. The size of p must generally be much larger resist long-term attack on discrete logs in Zp*.
Throughout the discussion we use the abbreviated notation “x” to mean exponentiation within some DH group. With respect to Zp*, “xz” is equivalent to (x raised to the power z) mod p”. We will also refer to subgroups of Zp* as Gx, where x is the order of the group.
The literature [PH78, McC90] discusses the proper selection of g and p, in particular to address the concern that easier solutions to the discrete logarithm problem make it easier to attack DH. Classical values for p and g in DH are where p=2q+1, q is also a large prime, and g is a primitive root of p. It has also been recommended to use values for g in DH that are generators of a smaller but still large subgroup of Zp* [P1363]. However, the available literature does not discuss how the structure of the group is particularly relevant to authentication systems that use DH. We explore this further in the detailed description of our invention.
In both [BM92] and [STW95] we find some analysis of the security of DH-EKE. [BM92] warns against allowing 0 to be used as an exponent. Attacks using other special numbers were, at that time, unknown. A variation of DH-EKE named M-EKE and general techniques for refining and strengthening the protocol against certain attacks are discussed in [STW95]. In the course of our invention, we uncovered a flaw in DH-EKE as described in the available literature. An analysis of this flaw and a means for correcting it are included in our method.